\documentclass[12pt,a4paper]{article}

\usepackage[12pt]{extsizes}

\usepackage[utf8]{inputenc}

\usepackage[russian]{babel}

\usepackage[OT1]{fontenc}

\usepackage{amsmath}

\usepackage{amsfonts}

\usepackage{amssymb}

\usepackage{algorithm}

\usepackage{algpseudocode}

\ifx\pdfoutput\undefined
\usepackage{graphicx}
\else
\usepackage[pdftex]{graphicx}
\fi

\usepackage{url}

\usepackage[usenames,dvipsnames]{color}

\usepackage[numbered,framed]{mcode}

\author{Королёв М.М}

\ifx\pdfoutput\undefined

\usepackage{graphicx}

\else

\usepackage[pdftex]{graphicx}

\fi

\begin{document}

\begin{center}

\vspace*{-4cm}

Минобрнауки России\\

Санкт-Петербургский государственный политехнический университет\\

Институт информационных технологий и управления\\

{\bf Кафедра измерительных информационных технологий}\\

\vspace*{8cm}

\Large Научно-Исследовательская работа:\\

"Security Games"

\end{center}

\vspace{\fill}

\begin{flushright}

Студент: Королёв М.М.\\

Преподаватель: Семёнов К.К.\\

\end{flushright}

\vspace*{3cm}

\begin{center}

Санкт-Петербург\\

2013 г.

\end{center}

\newpage

\tableofcontents

\newpage

\section{Вступление}

С каждым годом сфера применения теории игр расширяется всё сильнее. На данный момент, теория игр - эффективный инструмент для решения задач в области задач обеспечения безопасности. Игровые модели строятся на основе экспертного анализа и данных, полученных в ходе статистической обработки. Во многих случаях, неопределённость и неточность полученных данных разумно представлять в интервальном виде.

\section{Интервальный подход в решении задач \\ Security Games}

\subsection{Модель Штакельберга}

Для моделирования ситуаций, которые возникают в задачах обеспечения безопасности, удобно использовать модель Штакельберга. Как правило, теоретико-игровые модели рассматривают поведение двух игроков: предполагаемого атакующего, целью которого является завладеть теми или иными ресурсами, и защищающегося, цель которого - эти ресурсы защитить. Зачастую, стратегия защищающегося известна атакующему заранее и не является тайной: предполагается, что злоумышленник может предварительно провести наблюдения поведения защитника. При создании модели необходимо учитывать это обстоятельство. Модель Штакельберга предлагает следующую иерархию игроков:

первым о своей стратегии объявляет игрок 1, после этого стратегию выбирает игрок 2. Первый игрок называется лидером, второй - ведомым.

\subsection{Модель игр безопасности}

Предположим, защищающийся охраняет набор целей $\Theta_0$ $T = {\{t_1,....t_n\}}$  от атак злоумышленника $\Psi_0$, используя ограниченный набор ресурсов. Обозначим количество доступных ресурсов за m. Будем считать, что все ресурсы идентичны и могут быть использованы для защиты любой выбранной цели. Набор чистых стратегий атакующего $\sigma_\psi \in \sum_\psi$ заключается в выборе ровно одной цели из $T$. Каждая из стратегий защищающегося $\sigma_\theta \in \sum_\theta$ заключается в выборе подмножества целей T, размер которого меньше или равен m, которые защищающийся выбрал для распределения ресурсов. Рассмотрим взаимодействие атакующего и защищающегося в рамках модели Штакельберга. Защищающийся выбирает стратегию $\delta_\Theta$, которая является неким вероятностным распределением на области чистых стратегий из $\sum_\Theta$. Атакующий, оценив стратегию защитника $\delta_\Theta$, выбирает стратегию из  $\sum_\Psi$, дающую ему максимально возможный выигрыш.  Возможный выигрыш для каждой стороны зависит от того, какие из целей атакуются, и какие из них защищены. Например, при атаке на цель $t$ защищающийся получит выигрыш ${U_\Theta^u}(t)$ если цель не защищена и  ${U_\Theta^c}(t)$  в случае если цель под охраной. Выигрыши для атакующего вида $\omega \in \Omega$ можно обозначить как ${U_\Psi^u}(t,\omega)$  для незащищённой цели и ${U_\Psi^c}(t,\omega)$ для защищённой. Будем считать атаку на незащищённую цель удачной, а атаку на защищённую цель неудачной. Мы так же предполагаем, что ${U_\Theta^c}(t) \ge {U_\Theta^u}(t)$ и ${U_\Psi^u}(t) \ge {U_\Psi^c}(t,\omega)$ для всех $t \in T$. Для представления стратегии защищающегося введём понятие вектора покрытия целей, который представляет собой вероятность того, что тот или иной ресурс используется для защиты каждой цели. Эти вероятности для каждой цели $t_i \in T$ обозначаются как $c_i$, причём $\sum \limits_{i=1}^{n} c_i=m$. Общий вектор вероятности обозначим как $C$. 
 \subsection{Интервальный подход}
Интервальный подход позволяет расширить вышеизложенную модель. \cite{interval_uncertainty} Мы будем предполагать, что значения выигрышей атакующего и защищающегося лежат в некотором интервале и скорректируем модель, учитывая это обстоятельство.  При этом мы учитываем, что и атакующий и защищающийся знают точные значения своих выигрышей для каждой ситуации. Необходимость в интервальной оценке выигрышей защищающегося отсутствует, так как его стратегия является известной атакующему. 
Будем считать что значение ${U_\Psi^u}(t)$ лежит в неком интервале между ${U_\Psi^{u,min}}(t)$ и ${U_\Psi^{u,max}}(t)$, а значение  ${U_\Psi^c}(t)$  находится в интервале между ${U_\Psi^{c,min}}(t)$ и ${U_\Psi^{c,max}}(t)$. Защищающийся не знает ни точного значения  ${U_\Psi}(t)$, ни его распределения. Задача сводится к нахождению такого вектора $C$, который максимизирует выигрыш защитника в худшем возможном случае. 
Для каждой цели $t_i$ атакующий имеет диапазон возможных выигрышей:
\begin{equation} 
\upsilon^{max}(t_i) = c_i * {U_\Psi^{c,max}}(t_i) + (1-c_i) *  {U_\Psi^{u,max}}(t_i)
\end{equation}
\begin{equation} 
\upsilon^{min}(t_i) = c_i * {U_\Psi^{c,min}}(t_i) + (1-c_i) *  {U_\Psi^{u,min}}(t_i)
\end{equation}

Минимальный выигрыш, который может себе гарантировать атакующий, можно представить как максимальное значение из минимальных значений $\upsilon$. Обозначим это значение как $R=max_{t_i} \upsilon^{min}(t_i)$. Любая цель $t_i$ с максимальным предполагаемым значением $\upsilon^{max}(t_i) \ge R$ может быть лучшей целью для атаки.
Обозначим набор возможных целей атакующего как $\Lambda (C)$, определяемый следующим образом:
\begin{equation} 
\Lambda (C) = \{ t_i : \upsilon^{max}(t_i) \ge R  \}
\end{equation}

Тогда ожидаемый выигрыш защищающегося:
\begin{equation} 
d_i=c_i * {U_\Theta^c}(t_i)+(1-c_i) * {U_\Theta^u}(t_i)
\end{equation}
Задача защищающегося - выбор стратегии С, максимизирующей худший выигрыш для всех целей:
 \begin{equation} 
\max_{C}  (   \min_{t_i \in \Lambda(C) } d_i)
\end{equation}
 \subsection{Примерный алгоритм}
Стоит отметить, что максимальная возможная выгода защитника монотонно растёт с ростом доступных ресурсов m. Мы можем рассматривать задачу поиска оптимальной стратегии защитника как бинарный поиск в пространстве его ожидаемых выигрышей. На каждой итерации  мы будем оценивать возможность достижения предполагаемого размера выигрыша, учитывая количество доступных ресурсов. В случае невозможности, максимальный возможный выигрыш будет меньше или равен выбранному размеру выигрыша. Если предполагаемый выигрыш возможно получить, максимальный выигрыш больше или равен выбранному размеру. Используя этот подход, можно оценить максимальный выигрыш с заданным параметром ошибки. 
Для реализации этого алгоритма, необходимо оценить возможность получения того или иного выигрыша $D^*$ защитником. Так как мы анализируем худшие ситуации, мы должны гарантировать что защитник получит как минимум $D^*$ для любых значений выигрыша атакующего на выбранном интервале. Для этого, должно выполняться одно из двух условий для каждой цели:  
\begin{enumerate}
  \item {
	Цель находится в списке возможных целей $\Lambda (C)$, однако ожидаемый выигрыш защитника как минимум $D^*$.
	}
  \item {
	Цель не находится в списке возможных целей $\Lambda (C)$.
	}
\end{enumerate}

Оценим минимальный уровень покрытия $c_i$ для каждой цели:
 \begin{equation} 
c_i^1=\max\left(0,\frac {D^*-{U_\Theta^u}(t)}{{U_\Theta^c}(t)-{U_\Theta^c}(t)}\right)
\end{equation}

Для каждой цели рассчитываем значение $R$ и значение $c_i^1$. Для каждой цели мы так же можем оценить минимальный уровень покрытия $c_i^2$, который необходим, чтобы цель не оказалась в списке возможных целей $\Lambda (C)$: 

 \begin{equation} 
c_i^2=\max\left(0,\frac {R-{U_\Psi^{u,max}}(t)}{{U_\Psi^{c,max}}(t)-{U_\Psi^{c,max}}(t)}\right)
\end{equation}

Суммируя значения $c_i^1$ для целей из $\Lambda$ и $c_i^2$ для остальных целей, мы получим минимальное необходимое покрытие для получения выигрыша $D^*$.  

\section{Реализация алгоритма ISG на языке Matlab}
Алгоритм работы программы представлен ниже:

\begin{algorithm}
\caption{ISG алгоритм}\label{alg:Example1}
\begin{algorithmic}[1]
\ForAll {$t_i \in T$}  \State  $c_i \gets 0$  \EndFor
\State $maxPayoff\gets 0$
\State $lminPayoff\gets \min_{t_i \in T}(U_\Theta^c{(t_i)})$
\State $error\gets value$

\While{$maxPayoff-minPayoff\le error$}

\State $midpoint \gets (maxPayoff-minPayoff)/2$;


\If{ $\Call{feasibilityCheck}{midpoint,m,C}$}
\State $minPayoff\gets midpoint$
\Else
\State $maxPayoff\gets midpoint$
\EndIf
\EndWhile
\end{algorithmic}
\end{algorithm}

Функция feasibilityCheck:
\begin{algorithm}
\caption{feasibilityCheck}\label{alg:Example2}
\begin{algorithmic}[1]
\ForAll {$t_i \in T$}  
	\State  $c_i^1 \gets \max\left(0,\frac {D^*-{U_\Theta^u}(t)}{{U_\Theta^c}(t)-{U_\Theta^c}(t)}\right)$  
\EndFor
\ForAll {$t_i \in T$}  
	\State $totalCov \gets c_i^1$
	\State $c_i \gets c_i^1$
	\If {$c_i > 1$ }
	\State GOTO next $ t_i$
	\EndIf
\State {$R \gets (c_i^1 * U_\Psi^{c,min}(t_i))+(1-c_i^1)*U_\Psi^{u,min}(t_i)- \xi$} 
\ForAll {$t_j \in T\setminus t_i$}
\State {$c_i^2 \gets \max\left(0,\frac {R-{U_\Psi^{u,max}}(t)}{{U_\Psi^{c,max}}(t)-{U_\Psi^{c,max}}(t)}\right)$}
\State {$c_i^3 \gets \max\left(0,\frac {R-{U_\Psi^{u,min}}(t)}{{U_\Psi^{c,min}}(t)-{U_\Psi^{c,min}}(t)}\right)$}
\State {$minCov \gets \max(c_i^3, \min(c_i^1, c_i^2))$}
\If {$minCov < 0 \parallel minCov > 1 $}
\State GOTO next {$t_i$}
\EndIf
\State {$totalCov \gets totalCov+minCov$}
\State {$c_j \gets minCov$}

\If {$totalCov \ge m$}
\State \Return TRUE, $C$
\EndIf
\EndFor
\EndFor
\State \Return FALSE
\end{algorithmic}
\end{algorithm}

\newpage


\subsection {Исходный код}
     \begin{lstlisting}
    %Dramatis Personae
%T = {t1,t2...tn} - set of targets
%C = {c1,c2...cn} - set of probabilities of
% defending for each target
%Uud(t) - defender payoff for an attack
% on uncovered target
%Ucd(t) - defender payoff for an attack on
% covered target
%UuaMax(t) - attacker max payoff for an
% attack on uncovered target
%UuaMin(t) - attacker min payoff for an 
%attack on uncovered target
%UcaMax(t) - attacker max payoff for an 
%attack on covered target
%UcaMin(t) - attacker min payoff for an 
%attack on covered target
%R - maximum minimum value of attacker 
%expected payoff
%c1(t) - min defender coverage
% for target t
%c2(t) - min attacker coverage
% for target t
%c3(t) - mysterious constraint: 
%maximum attacker payoff
%e - error tolerance parameter for
% the binary search 
%m - count of available resources
function ISG_Algorithm()
   Tsize=7;
   m=4;
   e=0.0001;
   initPayoffsVariables();
   function initPayoffsVariables()
   QmaxA=18;
   QmaxD=20;
   DefAmax=7;
   DefDmax=8;
   DistMax=2;    
   DefD=rand(1,Tsize)*DefDmax; 
   Qd=(DefDmax+1)+rand(1,Tsize)*QmaxD; 
   Uud=(-Qd-DefD); 
   Ucd=(-Qd+DefD);
   Qa=(DefAmax+DistMax+1)+rand(1,Tsize)*QmaxA;
   DefA=rand(1,Tsize)*DefAmax; 
   Dist=rand(1,Tsize)*DistMax; 
   UuaMax=Qa+DefA+Dist;
   UcaMax=Qa-DefA+Dist;
   UuaMin=Qa+DefA-Dist;
   UcaMin=Qa-DefA-Dist;
   end
   Uud;Ucd;UuaMax;UcaMax;UuaMin;UcaMin;
   C=zeros(Tsize,1);
   maxPayoff=0;
   minPayoff=min(Uud);
   while (maxPayoff-minPayoff)>e 
       midPoint=maxPayoff+(minPayoff-maxPayoff)/2;
       %midPoint=(maxPayoff-minPayoff)/2; 
       [ret,C]=feasibilityCheck(midPoint,m,C);
       if strcmp(ret,'true')
            minPayoff=midPoint;
       else
           maxPayoff=midPoint; 
       end
   end 
   C
   midPoint
   min(Uud)
   function [ret,C]=feasibilityCheck(midPoint,m,C)
        c1=zeros(1,Tsize);
        for t=1:Tsize
          c1(t)= get_c1(t);
        end
        for t=1:Tsize
            totalCov=c1(t);
            C(t)=c1(t);
            if C(t)>1
              continue  
            end
            R=get_R(c1(t),t);
            for tj=1:Tsize
                if(t==tj)
                    continue
                end
                c2=get_c2(R,tj);
                c3=get_c3(R,tj);
                minCov=max([c3,min(c1(t),c2)]);
                if minCov<0 || minCov>1
                    break
                end
                totalCov=totalCov+minCov;
                C(tj)=minCov;
            end
            if (minCov>=0 && minCov<=1) && totalCov<=m
                ret='true';
                return 
             end
        end
        ret='false';
        return 
        function c1=get_c1(t)
            %cash=1-(midPoint-Uud(t))/(Ucd(t)-Uud(t));
            cash=(midPoint-Uud(t))/(Ucd(t)-Uud(t));
            c1=max([0,cash]);        
        end
        function c2=get_c2(R,t)
            %cash=1-(R-UuaMax(t))/(UcaMax(t)-UuaMax(t));
            cash=(R-UuaMax(t))/(UcaMax(t)-UuaMax(t));
            c2=max([0,cash]); 
        end
        function c3=get_c3(R,t)
            %cash=1-(R-UuaMin(t))/(UcaMin(t)-UuaMin(t));
            cash=(R-UuaMin(t))/(UcaMin(t)-UuaMin(t));
            c3=max([0,cash]); 
        end
        function R=get_R(c1,t)
            R=(c1*UcaMin(t))+((1-c1)*UuaMin(t)-e);
        end
    end
end

    \end{lstlisting}

\subsection {Пример вычисления ISG}
Рассмотрим гипотетическую ситуацию. 

Руководство крупной компании, занимающейся разработкой программного обеспечения, побывало на лекции ведущего эксперта по социальной инженерии Кевина. В результате беседы с экспертом, руководство решило заключить с ним контракт для проведения тренинга среди сотрудников с целью противодействия атакам со стороны возможных социальных инженеров.  Кевин изучил инфраструктура компании и выделил три возможные цели злоумышленника: 
\begin {enumerate}
\item отдел бухгалтерии с целью получения доступа к финансовой информации компании
\item отдел кадров с целью получения контактов инженеров для последующего переманивания их на лучших условиях
\item инженерный отдел с целью получения исходных кодов программ
\end {enumerate}

В процессе анализа выяснилось, что сотрудников каждого отдела можно разбить по группам, в зависимости от типа информации, к которой у них имеется доступ. В итоге было выделено три группы сотрудников бухгалтерии, две группы сотрудников отдела кадров и четыре группы инженеров. 


Кевин предложил провести тренинги для каждой группы. Однако, руководство компании, изучив стоимость услуг Кевина, пришло к выводу что текущего бюджета хватит на проведение только пяти занятий. Для оптимального распределения ресурсов Кевина между группами сотрудников было решено проконсультироваться у штатного специалиста по теории игр. 


Специалист обсудил с Кевином специфику прохождения такого тренинга. Выяснилось, что информация о таких тренингах редко остаётся секретной для злоумышленников, так что специалист пришёл к решению использовать модель Штакельберга.Для построения математической модели необходимо было оценить потери компании в случае утечки той или иной информации. По словам Кевина, в случае успешного прохождения тренинга сотрудник способен предотвратить утечку информации с вероятностью 65 \\%, однако необходимо учитывать общую техническую грамотность сотрудника. В итоге обсуждений были получены следующие оценки для каждой возможной цели:

\begin{table}[H]
\caption{\label{tab:company_payoff}Потери компании в случае утечки информации, *1000\$}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
  & $U_\Theta^u$ & $U_\Theta^c$ \\
\hline
buh1 & 35 & 25\\
buh2 & 20 & 10\\
buh3 & 15 & 8\\
hr1 & 12 & 6\\
hr2 & 15 & 10\\
dev1 & 40 & 25\\
dev2 & 35 & 15\\
dev3 & 25 & 10\\
dev4 & 14 & 8\\
\hline
\end{tabular}
\end{center}
\end{table} 

Так же важно было оценить заинтересованность злоумышленника в получении той или иной информации. Для этого совместно с Кевином была произведена оценка прибыли, которую может получить атакующий при атаке на каждую из целей:

\begin{table}[H]
\caption{\label{tab:attacker_payoff}Выигрыш атакующего в случае получения информации, *1000\$}
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
  & $U_\Psi^{u,max}$ & $U_\Psi^{u,min}$ & $U_\Psi^{c,max}$ & $U_\Psi^{c,min}$ \\
\hline
buh1 & 15 & 10 & 10 & 5\\
buh2 & 20 & 15 &  13 & 10 \\
buh3 & 5 & 2 & 2 & 1\\
hr1 & 10 & 8 & 6& 4\\
hr2 & 8 & 6 & 5& 3\\
dev1 & 35 & 25 &15& 10\\
dev2 & 25 & 15 & 10& 8\\
dev3 & 16 & 12 & 8 &4\\
dev4 & 12 & 19 & 8& 5\\
\hline
\end{tabular}
\end{center}
\end{table} 
Получив экспертные данные, специалист смог приступить к нахождению оптимального распределения сотрудников по тренингам:
\begin{table}[H]
\caption{\label{tab:training_distribution}Распределение сотрудников по тренингам, \%}
\begin{center}
\begin{tabular}{|c|c|}
\hline
  & С \\
\hline
buh1 & 0.9520\\
buh2 &  0.9520\\
buh3 &     0 \\
hr1 &      0\\
hr2 &      0\\
dev1 &  0.9840\\
dev2 & 0.9520\\
dev3 &   0.7200 \\
dev4 & 0.4400 \\
\hline
\end{tabular}
\end{center}
\end{table} 

\subsection {Моделирование выигрыша защитника при различном количестве ресурсов}
Существует возможность оценить зависимость выигрыша компании от количества проведённых тренингов. Для этого выполним моделирование, изменяя значение m. График зависимости можно наблюдать на рисунке 1:

\begin{figure}[h!]
  
  \centering
    \includegraphics [scale = 0.6] {images/payoff_test.eps}
\caption{Зависимость ожидаемого выигрыша защитника от количества доступных ресурсов.}
\end{figure}

Можно заметить, что выигрыш компании растёт с увеличением количества доступных ресурсов. Однако, при достижении m=6 выигрыш перестаёт расти. Это говорит о том, что проводить более 6 тренингов не имеет смысла. Так же, можно заметить, что выигрышы при m=5 и при m=6 отличаются незначительно, и решение руководства остановиться на 5 тренигах близко к оптимальному. 


\newpage

\section{Bayesian Security Games}
В случаях, когда существует неопределённость относительно типа атакующего, необходимо внести корректировки в рассматирваемую математическую модель. Как и раньше, в игре предполагается наличие двух игроков:
защитника $\Theta$ и атакующего $\Psi$. Набор целей $T= \{t_1,...t_i\}$ которые защищает защитник и набор ресурсов $R={r_1,...,r_m}$ которые защитник может использовать для защиты целей \cite{bayesian_stackelberg_games}.  
Для начала установим состояние равновесия для атакующего и защищающегося.
\begin{equation} 
\sigma_\Psi^*(C,\omega)= arg \max_{t \in T}(c_t * U_\Psi^c(t,\omega)+(1-c_t)*U_\Psi^u(t,\omega))
\end{equation}
Для определения состояния равновесия защитника мы определим функцию атаки $A(C)=(\alpha_t(C))_{t \in T}$ которая возвращает вероятности $\alpha_t(C)$ того, что каждая цель $t \in T$ будет атакована при заданном распределении типа атакующего и вектора покрытия $C$
\begin{equation} 
 \alpha_t(C) = \int\limits_{\omega \in \Omega} Pb(\omega)1_t(\sigma_\Psi^*(C,\omega))d \omega
\end{equation}
где $1_t(\sigma_\Psi^*(C,\omega))$ - функция-индикатор, которая возвращает 0 если $t=\sigma_\Psi^*(C,\omega)$ и $0$ в остальных случаях. Для заданной функции реакции атакующего  $A(\cdot)$ и набора всех возможных векторов покрытия защитника $C$, равновесное состояние для защитника может быть достигнуто при использовании смешанной стратегии оптимальной реакции $\delta_\Theta^* = C^*$
\begin{equation} \label{eq:best_response_strategy}
\delta_\Theta^* = arg \max_{C} \sum_{t \in T} \alpha_t (C) (c_t * U_\Theta^c(t)+(1-c_t)*U_\Theta^u(t))
\end{equation}
\subsection {Распределение выигрыша атакующего}
Так как множество типов атакующего бесконечно, вычисление выражения (\ref{eq:best_response_strategy}) невозможно напрямую. Чтобы разрешить эту проблему, мы заменим каждый выигрыш в основной модели вероятностным распределением возможных выигрышей. Для каждой цели $t /in T$ мы заменим значения $U_\Psi^c(t,\omega)$, $U_\Psi^u(t,\omega)$ для всех $\omega \in \Omega$ двумя функциями распределения:
\begin{equation} \label{eq:attacker_covered_function}
f_\Psi^c(t,r)=\int\limits_{\omega \in \Omega} Pb(\omega) U_\Psi^c(t,\omega)d\omega
\end {equation}
\begin{equation} \label{eq:attacker_uncovered_function}
f_\Psi^u(t,r)=\int\limits_{\omega \in \Omega} Pb(\omega) U_\Psi^u(t,\omega)d\omega
\end {equation}
которые отражают ожидания защитника о выигрыше атакующего. К примеру, защищающийся предполагает, что с вероятностью $f_\Psi^c(t,r)$ атакующий получит выигрыш $r$ при атаке цели $t$ когда цель защищена. Это открывает удобный путь для экспертов выражать неопределённость по поводу выигрышей в игровой модели, основанных на их собственной оценке или на основании полученных данных. Представим альтернативную формулу для выражения функции реакции атакующего. Для некоторого вектора $C$, пусть $X_t(C)$ - случайное значение, которое отражает ожидаемый выигрыш атакующего при атаке цели $t$, при заданном $C$. Тогда для каждой цели $t \in T$ верно:
\begin{equation} \label{eq:attacker_response_fin}
a_t(C) = Pb [X_t(C)]  > X_t'  \text{ для всех  }  t' \in T \setminus t]
\end {equation}
так как атакующий действует рационально. Формула (\ref{eq:attacker_response_fin}) может быть записана следующим образом:
\begin{equation} \label{eq:attacker_response_inf}
a_t(C) = \int\limits_{r=-\infty}^{r=+\infty} Pb[X_t(C)=r] \cdot \prod \limits_{t \in T \setminus t} Pb[X_{t'}(C)<r]dr
\end {equation}
\begin{equation*}
= \int\limits_{r=-\infty}^{r=+\infty} Pb[X_t(C)=r] \cdot \prod \limits_{t \in T \setminus t} \int\limits_{r'=-\infty}^{r'=r} Pb[X_{t'}(C)=r']dr' dr
\end {equation*}

Теперь мы можем попробовать определить случайные значения $X_t(C)$, использованные в формуле (\ref{eq:attacker_response_inf}). Значения $Pb[X_t(C)=r]$ для всех $t \in T$ и $-\infty < r <+\infty$. Представим каждое значение $X_t(C)$ используя две случайные величины, $X_t^-(C)$ и $X_t^+(C)$. $X_t^-(C)$. $X_t(C)$ описывает ожидаемый выигрыш атакующего в случае его атаки по защищённой цели, в то время как $X_t+(C)$ отражает ожидаемый выигрыш атакующего в случае атаки незащищённой цели при вектроре покрытия целей защитником C. Предположим так же, что $X_t(C)= r$  если $X_t^-(C)=x$ и $X_t^+(C)=r-x$ для некоторого $-\infty <x< +\infty$. Мы можем представить $Pb[X_t(C)=r]$ следующим образом:
\begin{equation*}
Pb[X_t(C)=r] = \int\limits_{x=-\infty}^{x=+\infty} Pb[X_t^-(C)=x] \cdot Pb[X_t^+(C)]=r-x]dx \\
\end {equation*}

\begin{equation*}
=\int\limits_{x=-\infty}^{x=+\infty} \frac{Pb[X_t^-(C)=x]dx*Pb[X_t^+(C)=r-x]dx}{dx} \\
\end {equation*}

\begin{equation*}
=\int\limits_{x=-\infty}^{x=+\infty} \frac{Pb[x \leq X_t^-(C) \leq x+dx] \cdot Pb[r-x \leq X_t^+(C) \leq r-x+dx]}{dx} \\
\end {equation*}

Если случайное событие приводит к выигрышу $y:= \frac{x}{c_t}$ с вероятностью $c_t$, ожидаемый выигрыш этого события $y \cdot c_t=x$. Тогда
\begin{equation*}
=\int\limits_{x=-\infty}^{x=+\infty} \frac{1}{dx}  \int\limits_{y= \frac{x+dx}{c_t}}^{y= \frac{x}{c_t}} f_\Psi^c(t,y)dy  \int\limits_{y= \frac{r-x+dx}{1-c_t}}^{y= \frac{r-x}{1-c_t}} f_\Psi^u(t,y)dy\\
\end {equation*}
Подставляя $u:=c_t y, v:=(1-c_t)$ получим
\begin{equation*}
=\int\limits_{x=-\infty}^{x=+\infty} \frac{1}{dx}  \int\limits_{u=x+dx}^{u=x} f_\Psi^c \left(t,\frac{u}{c_t}\right) \frac{1}{c_t} du  \int\limits_{v=r-x}^{v=r-x+dx} f_\Psi^u \left(t,\frac{v}{1-c_t}\right)\frac{1}{1-c_t} du 
\end {equation*}

\begin{equation*}
=\int\limits_{x=-\infty}^{x=+\infty} \frac{1}{dx} f_\Psi^c \left(t, \frac{x}{c_t}\right)\frac{1}{c_t}dx \cdot  f_\Psi^u \left(t, \frac{r-x}{1-c_t}\right)\frac{1}{1-c_t}dx 
\end {equation*}

\begin{equation*}
=\int\limits_{x=-\infty}^{x=+\infty} \frac{1}{c_t} f_\Psi^c \left(t, \frac{x}{c_t}\right) \cdot \frac{1}{1-c_t} f_\Psi^u \left(t, \frac{r-x}{1-c_t}\right)dx
\end {equation*}

Используя эту формулу для $Pb[X_t(C)=r]$ в  (\ref{eq:attacker_response_inf}) мы получим
\begin{equation*}
a_t(C) = \int\limits_{r=-\infty}^{r=+\infty} \int\limits_{r=-\infty}^{r=+\infty} \frac{1}{c_t} f_\Psi^c \left(t, \frac{x}{c_t}\right) \cdot \frac{1}{1-c_t} f_\Psi^u \left(t, \frac{r-x}{1-c_t}\right)dx dr 
\end {equation*}

\begin{equation*}
\cdot  \prod \limits_{t \in T \setminus t} \int\limits_{r'=-\infty}^{r'=r} \int\limits_{x=-\infty}^{x=+\infty} \frac {1}{c_t'} f_\Psi^c \left(t', \frac{x}{c_t}\right) \cdot \frac {1}{1-c_t'} f_\Psi^u \left(t', \frac{r'-x}{1-c_t'}\right) dx dr' 
\end {equation*}

Так же, запишем $a_t(C)=\int g_t \prod_{t' \in T \setminus t} G_{t'}$ где $G_t:=\int g_t$:
\begin{equation*}
\begin{split}
g_t(r):= \int\limits_{x=-\infty}^{x=+\infty} \frac{1}{c_t} f_\Psi^c \left(t, \frac{x}{c_t}\right) \cdot \frac{1}{1-c_t} f_\Psi^u \left(t, \frac{r-x}{1-c_t}\right)dx
\end{split}
\end {equation*}

Для вычисления $g_t$, $G_t$ и $a_t(C)$ мы можем использовать численные методы. В наших экспериментах мы протестируем два метода: первый использует Монте-Карло, второй кусочно-постоянную функцию для аппроксимации $f_\Psi^c$ и $f_\Psi^u$. 

\subsection{Методы решения задачи}
Для решения модели, описанной в предыдущей секции, нам необходимо найти равновесие Байеса-Штакельберга которое определит оптимальную стратегию покрытия целей ресурсами для защитника и оптимальную реакцию для каждого типа атакующего. Если существует конечное число типов атакующего, оптимальная стратегия защитника может быть найдена с помощью алгоритма DOBSS. К несчастью, нет никаких известных методов нахождения точных равновесных решений для бесконечных игр Байеса-Штакельберга, и DOBSS масштабируется только до малого количество видов атакующего. В статье фокусируются на методах аппроксимации решений для бесконечных игр Байеса-Штакельберга. Задача может быть разбита на две части:
\begin{enumerate}
  \item Вычисление и оценка функции реакции атакующего
  \item Оптимизация на множестве стратегий защищающегося при заданной функции реакции атакующего.
\end{enumerate}
\subsubsection{Монте-Карло}
Первый метод сочетает в себе сэмплы Монте-Карло из пространства типов злоумышленников с точной оптимизацией на множестве стратегий защитника. Этот подход основан на методе DOBSS для конечных игр Байеса-Штакельберга. Однако, мы так же внесём несколько улучшений от метода ERASER, который предлагает быстрое нахождение решения для задач security games. Результирующий метод может быть запрограммирован с помощью метода смешанного целочисленного программирования (MIP). Далее этот метод будем называть байесов ERASER. 
 Для использования байесова ERASER-а для поиска решений бесконечных игр мы выберем ограниченный набор типов атакующего из распределения типов, предполагая, что  каждый появляется с одинаковой вероятностью. Выигрыши для каждого типа определяются распределениями, описанными в формулах  (\ref{eq:attacker_covered_function}) и (\ref{eq:attacker_uncovered_function}).  Это приведёт к конечной игре, которая может быть решена с помощью байесова ERASER MIP. Будем называть этот метод Sampled Bayesian ERASER (SBE) и использовать сокращение SBE-x для обозначения этого метода с x видами типов атакующего. Последовательность равновесий полученных конечных игр будет сходится к равновесию оригинальной игры. В нашем случае, при стремлении количества типов атакующего в наборе к бесконечности, равновесие SBE-1 будет сходится к истинному Байесову равновесию Нэша.

\subsubsection{Жадный Монте-Карло}


Следующий алгоритм сочетает в себе жадную эвристику для распределения ресурсов защитника с очень быстрым методом обновления функции реакции атакующего с помощью выбора типа методом Монте-Карло. Будем называть этот алгоритм Жадный Монте-Карло (GMC). Идея жадной эвристики в том, чтобы начинать с вектора покрытия с предопределёнными нулевыми значениями вероятности для каждой цели. На каждой итерации алгоритм вычисляет перспективу (evaluates the prospect) добавляя небольшое приращение к вероятности покрытия каждой цели. Алгоритм вычисляет разницу между ожидаемым выигрышем защитника для текущего вектора покрытия C и нового вектора покрытия, который отличается только покрытием для одной цели $t$, так что $c_t^` = c_t + \Delta$. Цель с максимальным выигрышем для защитником выбирается, $\Delta$ добавляется к покрытию этой цели и алгоритм переходит к следующей итерации. 


Идея использования жадной эвристики для распределения вероятности покрытия вышла из части алгоритма ORIGAMI, который известен как оптимальный алгоритм для случаев без неопределённости о значениях выигрыша атакующего. Этот алгоритм в процессе выполнения последовательно определяет вероятности покрытия для набора целей, которые дают атакующему максимально возможный выигрыш. В случае байесовой игры нет чётко определённого набора целей с максимальным выигрышем для атакующего, так как каждый вид атакующего может иметь отличающуюся предпочтительную цель для атаки. Поэтому мы основываем стратегию на выигрыше защитника.   

В принципе, для реализации жадного алгоритма может быть использован любой метод оценки функции реакции злоумышленника. Однако, мы воспользуемся тем, что алгоритм требует добавления покрытия лишь для одной цели в единицу времени и реализуем очень быстрый алгоритм для оценки функции реакции атакующего. Мы начнём с алгоритма Монте-Карло для генерации большого количества типов атакующего. Для каждой цели мы получим список, содержащий отдельные виды типов атакующего, которые будут атаковать эту цель при заданном векторе покрытия. Для каждого типа мы будем отслеживать текущий ожидаемый выигрыш для каждой цели, лучшую цель для атаки и вторую цель по приоритету. Эти данные могут быть использованы для расчёта минимального покрытия, которое должно быть добавлено к текущему покрытию второй цели для того, чтобы атакующий сменил цель. Условие смены цели может быть записано следующим образом:
\begin {equation*}
\begin {split}
(c_{best} + \delta) U_\Psi^c(best,\omega) + (1-(c_{best} + \delta)) U_\Psi^u (best, \omega) \\
=(c_{secondt}) U_\Psi^c(second,\omega) + (1-(c_{second} ) U_\Psi^u (second, \omega) \\
\end {split}
\end {equation*}

Что приводит нас к:
\begin {equation} \label {eq: minimum_coverage}
\begin {split}
\delta = \frac{(c_{second}) U_\Psi^c(second,w) + (1-c_{second}) U_\Psi^u(second, \omega)}{U_\Psi^c (best,\omega)-U_Psi^u(best,\omega)} \\
- \frac{(c_{best}U_\Psi^c(bset,\omega)-(c_{best})U_\Psi^u(second,\omega)}{U_\Psi^c(best,\omega)-U_\Psi^u(best,\omega)}
\end {split}
\end {equation}

Используя эту систему, мы можем быстро рассчитывать изменения в ожидаемом выигрыше защитника добавляя $\Delta$ покрытие к цели $t$. Три фактора которые необходимо учитывать:
\begin{enumerate}
\item {
	Ожидаемый выигрыш защитника при атаке на t увеличивается
}
\item {
	Вероятность того, что атакующий выберет цель t может уменьшаться, так как некоторые типы атакующих не будут рассматривать цель $t$ как лучший вариант для атаки.
}
\item {
	Вероятность того, что другие цели будут атакованы может увеличиться, если те атакующие, которые атаковали цель $t$ выберут вместо неё другую цель.
}
\end {enumerate}

Для каждого типа в списке целей t мы определяем, изменится ли предпочтительная цель. Если тип изменяется, мы обновляем значение выигрыша для этого типа для того, чтобы ожидаемый выигрыш защитника соответствовал второй по приоритету цели для этого типа. Если нет, выигрыш против этого типа - новое значение ожидаемого выигрыша защитника для цели t с уровнем покрытия $c_t + \Delta$. После подстройки выигрыша для каждого типа, который атакует цель $t$ таким образом, мы получаем изменение ожидаемого выигрыша защитника добавляя $\Delta$ к цели t.

После расчёта потенциального изменения для каждой цели мы выбираем цель с максимальным приростом выигрыша для защитника и добавляем значения $\Delta$ к этой цели. Мы обновляем структуру данных, содержащую типы, обновляя ожидаемые значения изменённой цели для каждого типа. Если обновлённая цель была лучшей или второй по приоритету целью для выбранного типа, мы проводим перерасчёт лучшей и второй по приоритету цели и, если необходимо, переопределяем тип.

Основываясь на нашем опыте метода GMC мы так же добавили две модификации к алгоритму для предотвращения застревания в локальном оптимуме. Во-первых, мы поместили нижнюю границу в ${1\%}$  для $\Delta$, используемого в вычислениях для расчёта добавляемого покрытия каждой цели, не смотря на то что настоящий размер покрытия, необходимый для смены лучшей цели может быть куда меньше. Во-вторых, для случаев с очень малым количеством типов мы можем использовать оптимистичную версию эвристики, в которой мы предполагаем, что новые значения того или иного типа, который изменяет выбор цели, даёт максимум текущего значения или значение для новой цели (для защитника) Аргументом к этой эвристике является то, что предполагается возможность добавления дополнительного покрытия, которое может быть позже добавлено к второй по приоритету цели для переключения цели обратно. 

\begin{thebibliography}{2}

\bibitem{interval_uncertainty}
C. Kiekintveld, T.l Islam, V. Kreinovich,
  \emph{Security Games with Interval Uncertainty}.
 \emph{In AAMAS-3 2013 }.

\bibitem{bayesian_stackelberg_games}
C. Kiekintveld, J. Marecki, and M. Tambe.
 \emph{Approximation
methods for infinite Bayesian Stackelberg games: Modeling
distributional payoff uncertainty. In AAMAS-11, 2011.}


\end{thebibliography}
\end{document}